Igual que en la clase anterior, supondremos que $f(x)$ es una función continuamente diferenciable y que existe un valor $x^*$ donde $f(x^*)=0$ (es decir, $x^*$ es una raíz de $f$). Aquí abordaremos de nuevo cómo encontrar las raíces de $f$ dentro de un intervalo inicial $X$. Supondremos además que existe una extensión del intervalo $F'$ para la derivada $f'$, y que (por el momento) éste no contiene al cero: $0\notin F'(X)$.
La clave del método de Newton para intervalos está en aplicar el teorema del valor medio, que nos asegura que para cualquier $x\in X$ se cumple que
\begin{equation} f(x) = f(x^*) + f'(\xi) \cdot (x-x^*), \end{equation}para algúna $\xi$ entre $x$ y $x^*$. Aquí, $\xi$ es un valor desconocido, pero podemos utilizar el hecho de que está contenido en el intervalo: $\xi \in X$.
Por lo tanto, obtenemos
\begin{equation} x^* = x - \frac{f(x)}{f'(\xi)} \in x - \frac{f(x)}{F'(X)} =: N(X,x), \end{equation}donde hemos definido un operador $N$ que actúa sobre un intervalo y cualquier punto en el intervalo.
Si suponemos que $x^*\in X$, entonces $x^* \in N(X,x)\cap X$ para toda $x\in X$.
Una elección particular es $x = m := \mathrm{mid}(X)$, el punto medio del intervalo $X$. Entonces obtenemos el llamado operador de Newton para intervalos:
\begin{equation} N(X) := N(X,m) = m - \frac{f(m)}{F'(X)}. \end{equation}Nota que cuando implementamos esto en la computadora, en general $f(m)$ no se podrá calcular exactamente, por lo cual es necesario convertir $m$ en un intervalo $M := [m,m]$, y usar la extensión natural $F(M)$, así que tenemos finalmente
\begin{equation} N(X) := M - \frac{F(M)}{F'(X)}, \end{equation}donde ahora todos son intervalos.
Ahora podemos definir una sucesión de intervalos a partir de un intervalo inicial $X_0$, dada por $X_{k+1} := X_k \cap N(X_k)$. Por construcción, si $x^*\in X_0$ entonces $x^*\in X_k$ para toda $k$. Entonces, si $X_0$ contiene a una raíz, la raíz se mantiene dentro de la secuencia de intervalos, que de hecho forman una secuencia anidada que converge a $x^*$. Entonces, si controlamos que de alguna manera el diámetro de los intervalos $x_k$ disminuya, obtendremos cotas precisas para $x^*$. Esto es el contenido del Teorema del método de Newton para intervalos.
Más aún, si $f(x)$ es doblemente continua y diferenciable y $N(X)$ está bien definida en el intervalo $X$, se puede demostrar que
Si $N(X)\cap X = \emptyset$, es decir, $N(X)$ no se intersecta con $X$, entonces $X$ no contiene ninguna raíz de $f$.
Si $N(X) \subseteq X$, entonces $X$ contiene exactamente una raíz de $f$.
[1] Escribe una función que calcule el operador de Newton para un intervalo $X$, dadas $f(x)$ y $f'(x)$.
[2] Implementa el método de Newton para intervalos para encontrar las raíces de $f(x) = x^3 - 1$ a partir de $X=[-3,3]$. Muestra gráficamente la implementación del método. En cada iteración subsecuente del método, ilustra qué le pasa al diámetro de la refincación del intervalo que vas obteniendo.
[3] Usando tu implementación, demuestra que en el mismo intervalo $X=[-3,3]$ que $g(x) = x^2+1$ no tiene ninguna raíz. Ilustra gráficamente esto.
Hint: En el caso en que $0\in F'(x)$ las hipótesis del teorema no se cumplen. En ese caso hay que dividir el intervalo (bisección por ejemplo) y tratar de que las hipótesis del teorema se cumplan, para poder aplicarlo. Extiende tus funciones para que incluyan esta situación. En ese caso, cada subdivisión debe ser probada si puede o no tener una raíz.
[4] Considera la familia de polinomios de Wilkinson definidos por $W_n(x) = \prod_{i=1}^n(x-i)$. Partiendo de un intervalo simétrico alrededor de cero, implementa el método de Newton para encontrar sus raíces, utilizando diferenciación automática.
Hasta ahora, sólo hemos podido tratar el caso en el cual la derivada $F'(X)$ no contiene $0$. Sin embargo, resulta que es posible tratar también este caso, mediante "división extendida".
[5] Supón que $F'(X)$ sea un intervalo, digamos $F'(X) = [-a, b]$, que contiene $0$ (con $a, b > 0$).
(i) Definiendo $1/A$ como el conjunto $\{1/x: x \in A \}$, evalúa $1/F'(X)$.
(ii) Define una función que implementa esta "división extendida" de intervalos (o, más bien, inversa extendida).
[6] Resulta que el método de Newton sigue funcionando si utilizamos esta división extendida cuándo sea apropiado. Impleméntalo para encontrar todas las raíces de una función en un intervalo dado.
Nota que hay casos en los cuales no ocurre ninguna de las posibilidades (1) ni (2) en el teorema del método de Newton para intervalos. ¿Qué se puede hacer en este caso?
[7] Implementa pruebas (tests) para tu código.